1. Field of the Invention
The invention relates to a lookup method combining hardware with software and used in association databases. The invention applies to IPSEC(IP Security/RFC 2401) to accelerate the search for the correct key.
2. Description of the Related Art
There are two current technologies to deal with the SAD (Security Association Database) lookup method implemented by an ASIC (Application Specific Integrated Circuit) in an IPSEC (IP Security/RFC 2401) NIC (Network Interface Card). One such method is the “Hash Lookup” method while the other is the “Perfect Match Lookup” method.
These two technologies provide various methods for searching for a required key in an SAD to decrypt an incoming encrypted packet in a VPN (Virtual Private Network) environment.
While a complete SAD is located in the software level, a part of the SAD is maintained in the ASIC (i.e. an ASIC-SAD is a subset of a software-SAD). This principle lets the ASIC analyze the incoming packet and find the key the very first time. It is best if all of the possibly matched keys are located in the ASIC, and can be easily found by the ASIC without using the CPU. If such SAD arrangements and key search methods are not good enough, then the CPU must be used to search for the required key in the software level and the CPU must also update the ASIC-SAD. Thus, how to effectively search for the required key in the ASIC-SAD by the ASIC is a very important factor in improving the overall networking processing performance.
FIG. 1 is a block diagram of the SAD architecture. An incoming encrypted packet enters the ASIC, then the ASIC searches for the required key in the ASIC_SAD lookup section 10. If unsuccessful, the incoming encrypted packet is decrypted in the decryption section 30 after the required key is found with the help of a software_SAD 20.
A detailed explanation concerning “Hash Lookup” and “Perfect Match Lookup” will be next given as follows:
(1) Hash Lookup: This method calculates the 16-bit CRC (Cyclic Redundancy Code, named CRC16) of three specified items, which are D-IP (Destination IP address), IPP (IPSEC protocol) and SPI (Security Parameter Index) inside the encrypted packet, and the ASIC uses the CRC 16[x:0] as a pointer to perfectly match this item in the SAD (x=4, if the SAD totally has 16 items) as shown in FIG. 2 (i.e. each bit is compared; if the total bits of SAD_index are equal to 161, then the comparison is made 161 times).
If the SAD_index inside the pointed item that is called “bingo” is “perfectly matched” with D-IP, IPP and SPI, then the SAD_key of this item is the required key that can decrypt the encrypted incoming packet.
If the item inside ASIC is not “bingo”, then the software level updates the “bingo” item in ASIC. The algorithm is detailed as seen in FIG. 3.
The drawback of Hash Lookup is the “Hashing Hazard” problem. That is, two incoming packets with the same CRC16[x:0] require the software to update this “bingo” item frequently. For example, a packet 1 has the same CRC16[x:0] with a packet 2, but actually these 2 packets do not have the same SAD_index. If these 2 packets often arrive, then it causes the software level to update the “bingo” item quite frequently, which in turn lowers the overall performance of this system.
(2) Perfect Match Lookup: As shown in FIG. 4, the principle is to maintain a page in the ASIC, and this page is mapped to one of several pages in the software level. This method uses the 3 specified items (D-IP, IPP and SPI) within the encrypted packet to perfectly match those SAD_indexes inside SAD.
As illustrated in FIG. 5, the ASIC tries to perfectly match all items inside the ASIC_SAD. If the ASIC cannot find a match then the ASIC issues an interrupt to the software level that updates the ASIC_SAD inside the ASIC. This method requires a “smart software” to arrange a highly possible page for the ASIC; if this page is properly arranged, then the ASIC is easily “bingo”.
The method needs a very intelligent smart-software to arrange the “easy bingo page” in the ASIC. If some conditions are beyond the control of the software, it may cause the software to update the whole page in the ASIC frequently.
Updating the whole page in the ASIC costs the CPU lots of time if the coming encrypted packet is not “bingo” in the ASIC; therefore, the overall system performance is easily degraded.